This invention is in the field of digital data storage and retrieval. It relates more specifically to the storage and retrieval of large files of digital data that are typically either stored or retrieved as a continuous, uninterrupted stream.
It has become common to store music and movies as digital files. Digital film files in particular are typically larger than the digital files of other types of data. They also tend to be stored and retrieved in a particular manner. Digital music and video files are typically either retrieved or stored from start to finish as a continuous data stream. Although it is possible to stop the video or music at any time, it is more likely that the user will play an entire film or piece of music from start to finish. Even in the cases when the film or music is interrupted, large blocks of the digital files will be either stored or retrieved without interruption. For this reason, these files most often act as data streams and will discussed in this application as such. To recall and display or play either a digital film or digital song, the digital data must reach the system that will process it in a nearly continuous fashion, to prevent interruptions in its display or performance and to permit the most efficient storage of the digital file.
There are at least several other areas that generate digital data files that can be treated as data streams. These include medicine, including test results from Magnetic Resonance Imagery (MRI) or Computed Axial Tomography (CAT) scans, high-energy particle physics, satellite reconnaissance and other types of remote sensing. This list is not intended to be exhaustive. The techniques and apparatus described herein can be used to improve the management of any digital data file that comprises a large amount of digital data that is usually accessed and manipulated sequentially as a whole.
For purposes of this specification, the digital file of a film, song, picture or other data (see the preceding paragraph) is called herein a data stream. Although streaming data has so far been used to describe video and audio digital data, any sufficiently large file of digital data, including pictures, text and the like, may act like and require the same treatment as a data stream.
As data streams have become more and more common, computer systems are increasingly expected to adequately service such data streams. Such service will typically consist of properly supporting the data stream while responding with reasonable speed to a series of asynchronous, essentially random data accesses. In the near future, computer systems will probably be required to handle multiple data streams simultaneously. Although retrieving and processing a single data stream corresponding to a single video places large demands on the storage and retrieval devices of whatever system is assigned to this task, most current computer systems handle a single data stream and some amount of asynchronous random data requests reasonably well. However, retrieving and displaying or storing multiple data streams simultaneously is extremely resource intensive. Known systems typically do not handle multiple data streams well.
The most common mass storage medium in a computer system is a hard disk drive. As hard disk drives are known in the art, only those aspects of their construction and operation that are particularly relevant to the present invention will be discussed here.
A hard disk drive typically comprises a spindle motor and one or more disk coated with magnetic material, the disks being attached to the spindle motor and rotated by it. The disks typically have a plurality of concentric recording tracks. A plurality of transducers, usually one per usable disk surface, for reading and recording data on the disks are attached to a series of transducer arms which position the transducers over the specified track of the disks. In turn, the transducer arms are attached to a servomechanism that radially positions the transducer arms. A buffered data path is then provided for transferring data between the transducers and the disk interface. Finally, the separate elements are all under the control of one or more sequencers or microprocessors which electrically couple and control the spindle motor, the transducers, the servo mechanism and other related systems, including an error correction code system. At least one disk surface has positioning signals thereon, which signals provide the servomechanism with location reference information allowing for the proper positioning of the transducers arms.
In terms of data processing, the typical disk drive comprises a cyclical, multi-tracked storage medium for digital data which, in response to external read and write requests, either establishes a buffered path to and copies data from at least one logical block address (LBA) location on the multi-tracked storage medium identified by each read request or establishes a buffered path to and records data to at least one LBA location on the multi-tracked storage medium identified by the write request. It is possible to arrange storage on the disk(s) as one or more continuous spiral tracks beginning at the maximum outer diameter of the disk that the transducer can reach and extending to the minimum inner diameter of the disk and interlaced as necessary. This is not typically how data is stored on disks today, but could be utilized in a data stream environment. The present invention description can operate equally well with either arrangement of data tracks on disks.
Proper control of the buffers between the disk drive's transducers and the disk drive's interface with the computing environment it is coupled to is essential to insure smooth transfer of data to and from the disk drive.
In the case of data streams, proper allocation of the disk drive's buffers (also called “caches” herein) and proper operation of its microprocessor controls are needed to effectively support a single data stream and multiple asynchronous random accesses or multiple data streams simultaneously or some combination of both. Although most disk drives support a single data stream reasonably well, even with some level of random accesses, multiple data streams are managed much less successfully. Most disk drives do not or cannot recognize data streams mixed with other data types and, as a result, their relatively low transfer rates and inefficient internal resource allocation makes them poor data stream managers.
Known caching schemes do not make specific efforts to support data streams beyond sequential storage access, both in terms of Logical Block Addresses (LBAs) and access time. Once a data stream has begun (this cannot accurately be described as “requested” as operating systems do not typically address the problems of data streams), it may or may not be properly serviced, the servicing depending on the size of the cache allocated to sequential data and the actual address sequences of the accesses. As no specific effort is made to identify whether a set of commands (which will not necessarily be a linear sequence of LBAs) references a data stream, no effort is or can be made to service one or more such data streams as data streams. The most commonly used computer operating systems currently service only one data stream properly.
Certain storage systems which use queues, including SCSI disc drives, recognize that a series of input/output (I/O) requests can be bundled together, possibly re-ordered and then sent to the disk drive as a single request. This approach does not address the need to front load the drive's read cache to insure that all I/Os are within the cache and eliminate the need to wait for a physical disk drive I/O, or the need to free the write cache in advance of an end user request, both of which are minimal requirements to support one or more data streams adequately.
Most storage systems, including disk drives, simply use a large cache and assume that this will be adequate to support data streams. Unfortunately, when multiple data streams and random commands mix or if there are disk problems, the data streams are typically not serviced adequately. In those cases where a data stream is actually recognized, management of multiple data streams in the data storage system is usually handled in one of two ways. Either the data streams are serviced in a round robin manner, where each data stream is serviced in turn, or a data stream gets priority service when the system determines that there is insufficient data “on hand” to support the continuation of the stream safely. In this context, servicing means that data is either read from the disk and placed into the buffer to support the data stream or data is placed in the buffer preparatory to being written to the disk. Neither the round robin nor “starvation” support scheme allows proper servicing of multiple data streams.
A round-robin approach, where each data stream is serviced in turn, fails when the data streams have different throughputs, as can occur at either the storage level, where the disk drive handles some data streams faster than others (one data stream is accessing data from the drive's inner diameter and another data stream is accessing data from the drive's outer diameter), or at the user level, where one user is accessing both an MP3 data stream and an MPEG2 data stream at the same time. The determination of which data stream needs to be serviced next cannot be static, but must be adjusted dynamically. The round-robin approach is a static one, and usually results in one or more data streams losing support.
Further, the round-robin support scheme is extremely wasteful in that the disk drive's transducers are moved across the disk to access different sectors too often while servicing the different data streams. The time lost in moving the transducers can lead to a condition called herein “thrashing,” where data streams begin to starve for data while the system moves the transducers to different disk areas to service each data stream successively. The failure of the round-robin support scheme stems from the failure to recognize that different data streams require different amounts of support in any given time interval.
The “starvation” scheme can also lead to thrashing for similar reasons. The starvation method of support scheduling, also known as “deadline scheduling,” focuses on scheduling support for processes (data streams in the present invention) when they have reached a trip-level or deadline and ignoring them otherwise. This approach, with some added complexities, has been the mainstay of operating system scheduling since the 1960s. When applied to data streams, this method would assign attention to a given data stream when its remaining buffered time drops below a certain level. Various levels would require different levels of attention.
Unfortunately this approach in practice keeps the global system as close to collapse as possible, only acting when an action is required instead of acting when an action is possible. A system using this approach must be carefully tuned for the specific set of applications it runs, or over-designed to support any possible set of applications, or the least delay in data retrieval will cause its collapse.
Proper data stream management further requires that the difference between random and data stream cache access patterns be recognized. In a random series of commands, data stored in the cache may be reused. In a data stream, it is very unlikely that data will be reused. Therefore, there must be a different replacement algorithm for the sequential (data stream) and random access portions of the cache.
Some known disk drives, when the drive controller determines that the current command is a sequential read, “post fetch” data, usually up to the end of the current disk track. “Post fetch” is useful as it is based on the known statistical likelihood that the “post fetched” data will be needed. “Post fetch” remains a method for improving response to a single data stream. It does not provide a successful method for dealing with multiple data streams. Other known disk drives have used different cache storage methods for sequential and random data.
Despite the recognition by some storage device manufacturers that sequential data streams need to be handled very differently from random data so as not to flood or starve the random cache, little has been done to solve the problems associated with cache starvation or flooding, which servicing multiple data streams can occasion. At best, known methods manage random accesses, some of which happen to be spatially sequential.
U.S. Pat. No. 6,038,619 recognizes a single data stream that comprises either purely sequential or near sequential read or write requests. This recognition permits using a circularly buffered data path to support the data stream. The '619 patent recognizes only a small subset of the command sequences that can be data streams, it does not recognize the need or possibility of supporting multiple data streams at the same time, makes no provision for considering the throughput needs of a data stream and does not consider how to detect the end of a data stream.
Further complications arise when the data storage system must deal with multiple data streams at the same time, or when the system must deal with both random accesses and data streams at the same time. In these cases, the system will typically stop recognizing the data stream as a sequential data stream and cease post-fetching it. This dramatically reduces the data throughput available to support the data stream. Even with a single data stream, if the stream commands do not come in synchronously, the drive will halt its post-fetch at some point, which eventually results in a delay in the data transfer as the drive waits for needed data to pass again under its read-write transducers. Similarly, when the cache fills up, no further “post-fetching” is attempted, as there would be no place to store the fetched data. However, by ceasing to “post-fetch,” the system has essentially stopped recognizing the data streams, eliminating whatever improved data stream handling had been achieved.
Known data stream management systems and methods also fail when data streams end. No known system or method actively attempts to detect the end of a data stream. At best, the controller in a disk drive might detect that commands are no longer in approximate LBA order. This detection does not occasion any formal procedure to terminate support of the data stream.
Without recognizing that individual data streams may require variable amounts of data over time and that different data streams have different data requirements over the same time period, there cannot be any effective means for managing multiple data streams either alone or in combination with random accesses. This awareness of data stream throughput requirements is missing from any known system or method of data stream management.
For example, if one loads four large images or files, today it is better to request the loading of these files one after the other, rather than requesting them all simultaneously. The time difference between these two approaches is significant, the delay associated with simultaneous loading being caused by thrashing between the four data streams.
With more typical data streams, including audio and video files, where uninterrupted throughput is essential, as stream data must be delivered on time, not late, similar problems arise if simultaneous, rather than sequential access is requested. A computer operating system cannot be relied upon to deliver commands sequentially in these cases. Delivering uninterrupted support for data streams in these environments thus becomes virtually impossible with known systems and methods.
A method and system for supporting multiple data streams simultaneously would represent a significant improvement over the known art.